//===----------------------------------------------------------------------===//
//
//                         BusTub
//
// lru_k_replacer.cpp
//
// Identification: src/buffer/lru_k_replacer.cpp
//
// Copyright (c) 2015-2022, Carnegie Mellon University Database Group
//
//===----------------------------------------------------------------------===//

#include "buffer/lru_k_replacer.h"
#include <cstddef>
#include <ctime>
#include <limits>
#include <mutex>
#include "common/exception.h"

namespace bustub {

LRUKReplacer::LRUKReplacer(size_t num_frames, size_t k) : replacer_size_(num_frames), k_(k) {}

auto LRUKReplacer::Evict(frame_id_t *frame_id) -> bool {
  const constexpr size_t inf = std::numeric_limits<size_t>::max();
  int ans_id = -1;
  size_t k_distance = 0;
  size_t earliest_time = inf;

  std::scoped_lock<std::mutex> lock(latch_);
  for (auto &[id, node] : node_store_) {
    if (not node.is_evictable_) {
      continue;
    }
    size_t distance = inf;
    size_t last_time = inf;
    const auto &his = node.history_;
    if (his.size() >= k_) {
      distance = current_timestamp_ - his.front();
    }

    if (!his.empty()) {
      last_time = his.back();
    }
    if (distance > k_distance) {
      ans_id = id;
      k_distance = distance;
      earliest_time = last_time;
    } else if (distance == k_distance) {
      if (last_time < earliest_time) {
        earliest_time = last_time;
        ans_id = id;
      }
    }
  }

  if (ans_id != -1) {
    --curr_size_;
    // node_store_[ans_id].history_.clear();
    node_store_.erase(ans_id);
    *frame_id = ans_id;
    return true;
  }
  return false;
}

void LRUKReplacer::RecordAccess(frame_id_t frame_id, [[maybe_unused]] AccessType access_type) {
  if (static_cast<size_t>(frame_id) > replacer_size_) {
    throw Exception("recording non-exist frame");
  }
  std::scoped_lock<std::mutex> lock(latch_);
  if (node_store_.count(frame_id) == 0) {
    node_store_[frame_id] = LRUKNode();
    // node_store_[frame_id].fid_ = frame_id;
  }
  node_store_[frame_id].history_.push_back(current_timestamp_++);
  if (node_store_[frame_id].history_.size() > k_) {
    node_store_[frame_id].history_.pop_front();
  }
}

void LRUKReplacer::SetEvictable(frame_id_t frame_id, bool set_evictable) {
  std::scoped_lock<std::mutex> lock(latch_);
  if (node_store_.count(frame_id) == 0) {
    throw Exception("setting non-exist frame");
  }
  LRUKNode &node = node_store_[frame_id];
  if (node.is_evictable_ != set_evictable) {
    node.is_evictable_ = set_evictable;
    curr_size_ += set_evictable ? 1 : -1;
  }
}

void LRUKReplacer::Remove(frame_id_t frame_id) {
  std::scoped_lock<std::mutex> lock(latch_);
  if (node_store_.count(frame_id) == 0) {
    return;
  }
  if (!node_store_[frame_id].is_evictable_) {
    throw Exception("removing non-evictable frame");
  }
  node_store_.erase(frame_id);
  --curr_size_;
}

auto LRUKReplacer::Size() -> size_t { return curr_size_; }

}  // namespace bustub
